package 双指针法;

import com.alibaba.fastjson.JSON;
import common.GeneralFunction;

import java.util.*;

public class No15三数之和 {

    /**
     * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，
     * 使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
     *
     * 注意：答案中不可以包含重复的三元组。
     * 示例：
     * 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
     * 满足要求的三元组集合为：
     * [
     *   [-1, 0, 1],
     *   [-1, -1, 2]
     * ]
     */

    /**
     * 这个为什么比我good呢?是因为它的两个指针都在i的右边(left=i+1),比我少遍历了一些
     * 而我在一左一右,完全是没必要的,因为一路遍历下来左指针会有重复的操作
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSumGood(int[] nums) {// 总时间复杂度：O(n^2)
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length <= 2) return ans;

        Arrays.sort(nums); // O(nlogn)

        for (int i = 0; i < nums.length - 2; i++) { // O(n^2)
            if (nums[i] > 0) break; // 第一个数大于 0，后面的数都比它大，肯定不成立了
            if (i > 0 && nums[i] == nums[i - 1])
                continue; // 去掉重复情况
            int target = -nums[i];
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] == target) {
                    ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));

                    // 现在要增加 left，减小 right，但是不能重复，比如: [-2, -1, -1, -1, 3, 3, 3], i = -2, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3
                    //首先无论如何先要进行加减操作
                    //因为当前是排序的,两者等于一个数,那么仅一个的值增加或减少,那么就肯定不会等于这个数
                    left++; right--;
                    while (left < right && nums[left] == nums[left - 1])
                        left++;
                    while (left < right && nums[right] == nums[right + 1])
                        right--;
                } else if (nums[left] + nums[right] < target) {
                    left++;
                } else {  // nums[left] + nums[right] > target
                    right--;
                }
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        int[] arr=new int[]{-1,0,1,2,-1,-4};
        GeneralFunction generalFunction=new GeneralFunction(No15三数之和.class,arr);
        generalFunction.runAllMethod();

    }

}
